package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-30 22:40
 **/
public class LeetCode990 {

    /**
     * 使用Quick-Union实现并查集
     * @param equations
     * @return
     */
    public boolean equationsPossible(String[] equations) {
        //使用数组充当并查集的数据结构,由题可知,只有26个小写字母充当变量,故定义长度为26的数组,映射26个小写字母
        int[] parent = new int[26];
        //并查集初始化,初始每个节点的根节点指向自身
        for (int i = 0; i < 26; i++) {
            parent[i] = i;
        }

        //先遍历一次数组equations,将相等的两个变量合并, "=="充当边
        for (String str : equations) {
            if (str.charAt(1) == '=') {
                //获取字母映射的索引
                int index1 = str.charAt(0) - 'a';
                int index2 = str.charAt(3) - 'a';
                //并查集合并两个节点,即将index1节点的根节点指向index2的根节点
                union(parent, index1, index2);
            }
        }

        //再次遍历一次数组equations,如果判断不等的情况下,两个节点的根节点不能相同
        for (String str : equations) {
            if (str.charAt(1) == '!') {
                int index1 = str.charAt(0) - 'a';
                int index2 = str.charAt(3) - 'a';
                if (find(parent, index1) == find(parent, index2)) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 合并方法,将index1的根节点指向index2
     * @param parent
     * @param index1
     * @param index2
     */
    public void union(int[] parent, int index1, int index2) {
        parent[find(parent, index1)] = find(parent, index2);
    }

    /**
     * 并查集查找方法实现,找到节点index的根节点
     * @param parent
     * @param index
     * @return
     */
    public int find(int[] parent, int index) {
        while (parent[index] != index) {
            index = parent[index];
        }
        return index;
    }


}
